; bakery.asm
;
; Contains x64 assembly source for bakery algorithm entry/exit routines on the Microsoft
; Windows platform.
;
; Author: Aidan Goddard, 22/6/13
;
;
; MICROSOFT x64 FASTCALL CONVENTIONS:
; RCX, RDX, R8, and R9 for parameters (int)
; RAX, R10, R11, XMM4, and XMM5 are considered volatile. the rest must be preserved
;
; see http://en.wikipedia.org/wiki/Lamport's_bakery_algorithm
;
; this is a slightly modified version of the algorithm - on entering, instead of 
; scanning through all of the thread ticket numbers to get the largest, it mearly checks
; a variable that shows what the last assigned ticket number was. This is faster (a lot faster),
; but has the drawback that ticket numbers don't reset to 0 when there is no activity in the
; critical region. This, however, isn't an issue as (signed) 64-bit containers are used so,
; if the critical region was accessed 3,000,000,000 times a second (as if!), the algorithm
; would still be operational after 50 years of continuous activity. Considering the longest time
; current hardware could deal with being utilized at 100% would be < 10 years, I guess 50 years
; is long enough.
;
; However, 50 years could be limiting on future projects (deep space crafts travelling for 100+ years?),
; so future work-arounds will be discussed.
; 
; UPDATE 23/6/13:
; 
; The entering routine has been updated to remove the dependancy on the highest current ticket variable
; and allow the system to [possibly] run indefinately.
;
; NOTE 24/6/13:
;
; If a thread enters, but does not exit and then attempts to re-enter, it will still be accepted the second time.
; The reasons for this occuring are mainly due to limitations of the algortithm. This should not prove to be an
; issue as the cases where this occurs usually come about when the programmer simply forgets to call BakeryLeave()
; after every BakeryEnter(). This makes this implementation a reentry-compatible lock.
;
;******************************************************************************************
; application bakery data structure description
; should be 8-byte aligned for performance benefits and zeroed on start
;
; 0		: DWORD * 256 : entering values (0 = false, 1 = true)
; 1024	: DWORD * 256 : ticket numbers
; 2048	: DWORD		  : highest current ticket value
; 2052  : DWORD		  : thread count
; 2056	: 2040		  : reserved
; total size = 4096 bytes (4k)
;
;******************************************************************************************

.code

;******************************************************************************************
; bakery setup function
; arg1 rcx -> thread count
; arg2 rdx -> ptr to structure

BakerySetup proc
	; zero everything
	mov		r10, rcx		; save thread count
	mov		r11, rdx		; save base ptr
	mov		rcx, 1024		; set for number of DWORDs to write
	mov		eax, 0			; value to write (zero)

	; main zero-ing loop
	zero_loop:
		mov		[rdx], eax				; write the DWORD
		add		rdx, 4					; increase the pointer to the next DWORD
		loop	zero_loop				; loop until done

	; done zero-ing
	; now save thread count
	add		r11, 2052					; add offset to thread count
	mov		[r11], r10d					; save thread count to structure (low DWORD)

	; finished, return
	ret;
BakerySetup endp

;******************************************************************************************
; bakery entry/lock function
; arg1 rcx -> thread number (0 - 256)
; arg2 rdx -> ptr to bakery data structure
; returns rax -> ticket number used

BakeryEnter proc
	; first set the entering value for this thread
	lea		r9, [(rcx * 4) + rdx]		; get address of entering value
	mov		[r9], DWORD PTR 1			; move a 1 to that address
	sfence

	; get the highest ticket number
	lea		r10, [(rcx * 4) + rdx + 1024]	; get address of holder for this ticket number
	lea		r11, [rdx + 2048]				; get address of highest ticket number
	mov		eax, [r11]						; get highest ticket number
	inc		eax								; increase it
	mov		[r10], eax						; save it to this thread's ticket
	mov		[r11], eax						; save it to highest ticket number

	; set entering to false
	mov		[r9], DWORD PTR 0			; move 0 to the entering value
	sfence


	; setup for per-thread loop
	; r8 = ptr to entering array (start at base)
	; r9 = ptr to ticket array (start at base)
	; r10 = thread id counter (starts at 0)
	; r11 = current thread id
	; rcx = thread count (used for loop)
	mov		r8, rdx					; get entering array base
	lea		r9, [rdx + 1024]		; get tickets array base
	mov		r10, 0					; start on thread 0
	mov		r11, rcx				; get current thread id
	lea		rcx, [rdx + 2052]		; get address of max number of threads
	mov		ecx, [rcx]				; get number of threads
	
	; for each thread
	thread_loop:
		; check if this thread
 		cmp		r10, r11				; compare this thread id with the current thread id
		je		thread_loop_skip		; if they equal, skip to next one
		
		; this thread is not the current thread
		; enter choosing-wait loop
		choosing_loop:
			lea		rax, [(r10 * 4) + r8]	; get address of choosing variable
			mov		eax, [rax]				; get the value
			or		eax, eax				; or eax with itself to set the zero flag if it's zero
			pause							; relax a bit
			jnz		choosing_loop			; if choosing variable is 1, try again

		; finished choosing loop
		; enter ticket check loop
		ticket_loop:
			lea		rax, [(r10 * 4) + r9]	; get address of this ticket
			mov		eax, [rax]				; get this ticket value
			or		eax, eax				; or it with itself to check for zero
			jz		ticket_loop_leave		; is zero, can leave this loop

			lea		rdx, [(r11 * 4) + r9]	; get address of current ticket
			mov		edx, [rdx]				; get current ticket value
			cmp		edx, eax				; compare current ticket value with this ticket value
			jg		ticket_loop				; if current ticket value is larger than this ticket value, loop

			;(ticket.get(tid) == ticket.get(i) && tid > i)
			jne		ticket_loop_leave		; if current ticket value is not equal to this ticket value, leave

			cmp		r11, r10				; compare current thread id with this thread id
			jg		ticket_loop				; if current thread has a higher id with this thread, loop. Otherwise leave.

		ticket_loop_leave:

	thread_loop_skip:
		inc		r10					; make r10 point to next thread
		loop	thread_loop			; if more threads to check, check the next one

	; finished loop, return
	lea		rax, [(r11 * 4) + r9]		; get address of ticket number
	mov		eax, [rax]					; get ticket
	ret
BakeryEnter endp

;******************************************************************************************
; bakery leave/unlock function
; arg1 rcx -> thread number (0 - 256)
; arg2 rdx -> ptr to bakery data structure

BakeryLeave proc
	; make sure all critial section accesses are committed
	mfence

	; set the ticket for this thread to zero
	lea		r11, [(rcx * 4) + rdx + 1024]	; get address for the ticket number for this thread
	xor		eax, eax						; clear rax to zero
	mov		[r11], eax						; zero the ticket value
	sfence

	; finished, return
	ret
BakeryLeave endp

; marks the end of the file
END